Consider a user who views a Web page at a news site at 10:00 a.m., and then visits it again at 11:00 a.m. Although there are some updates during this time, the Web page at 11:00 a.m. is largely the same as it is at 10:00 a.m. However, despite the common content between the pages at 11:00 a.m. and 10:00 a.m., in current implementations, the user's computer 100 downloads the entire page from the news site both times. This results in the inefficient utilization of network bandwidth between the user and the news site, creating network congestion and long download times.
The above situation is compounded by the fact that users often view the same page at the same site several times a day. To improve this situation, Internet Service Providers (ISPs) often deploy cache servers at various points in the network for storing frequently accessed content. For example, America Online (AOL) currently utilizes Inktomi's Traffic Server, a network caching platform, to speed up Web access for its users. When a user requests a Web page, the request is routed to the closet cache server in the network. If the requested Web page is located in the cache and is current, then the cache server delivers the page directly to the user without the need to access the Web server. By eliminating redundant network traffic between the cache server and the Web server, the cache server accelerates the delivery of content.
However, these cache servers suffer several limitations. First, cache servers do not reduce network delays between the cache server and the user. Additionally, cache servers are designed to exploit spatial correlation among multiple users. That is, a cache server is most effective when its contents are accessed by many users. As such, cache servers are not designed for and do not have the capacity to handle personalized content that is unique to every user. Finally, a cache server is only effective as long as its content remains current. Thus, cache servers cannot handle dynamically generated content that changes with time. It is not efficient to cache dynamically generated content since, by definition, such content will change upon subsequent retrievals.
The user's Web browser also employs a local cache for content that is repeatedly loaded in unchanged form into the browser. For example, browsers often cache image files, such as customized buttons, that make up part of a Web page. Both browser caches and network caches maintain the validity of their cached objects using hash and time-stamp verification. Specifically, when a cache receives a request for a cached object, the cache may verify the validity of the object by transmitting a binary time stamp of the cached object to the content server. The content server compares the transmitted value to that of its corresponding object. If the two values are equal, the content server signals the browser to load its own cached copy. If the two values are different, the content server sends a fresh copy of the object to the cache. Since transmission of a binary time-stamp of an object consumes significantly less bandwidth than transmission of the entire object, caches reduce network traffic between the cache and the content server. However, neither local caches nor cache servers can provide an adequate solution for access to the dynamically generated content that is so pervasive on modern networks.
Another technique to reduce network congestion is data compression. Files embedded in Web pages may be compressed using a data compression algorithm. For example, text files may be compressed using the Lempel-Ziv encoding algorithm, image files may be compressed using JPEG encoding, and digital audio and video files may be compressed using MPEG encoding. By transmitting files through the network in compressed form and decompressing them upon receipt by the user's browser, network bandwidth is efficiently utilized. Unfortunately, data compression as presently implemented only exploits the redundancies within a single web item, but not across multiple items that may be variations of the same item over time, or otherwise related to each other.
While data compression algorithms may not exploit redundancies between files, certain such algorithms do teach exploitation of redundancies between similar portions (for example, video frames or audio blocks) within a file. These compression algorithms use a variety of different techniques to exploit correlation within and across frames (or blocks) in order to reduce the number of bits required to represent an entire sequence of such frames. For example, in video compression, a predetermined sequence of video is decomposed into a series of frames, each frame comprising a still image. Digital audio is similarly processed, by breaking up the sequence into a series of blocks, each of which represents a predetermined time interval. The sequences must be predetermined because each frame is compressed by using information from its preceding or subsequent frames. These compression algorithms require frames to be reconstructed in the same order by all users. For this reason, such data compression algorithms cannot apply to the network situation where different users may demand different documents over randomly chosen time intervals and in random order.
Therefore, as discussed, caches do not offer an adequate solution to the problem of accelerating the delivery of dynamically generated and personalized content in a networked environment. Furthermore, data compression teachings for exploiting redundancies between frames or blocks in a single file do not apply well to exploiting redundancies between randomly accessed but similar (e.g. dynamically generated) files in a network. Thus, there remains a need for accelerating the delivery of content in a networked environment.